package com.lili.dt;

/**
 * @Auther: 李 力
 * @Date: 2024/8/8
 * @Description: 完全背包问题
 * @version: 1.0
 */
public class AllBaiBao {
    /*
1. n个物品都是固体，有重量和价值
2. 现在你要取走不超过 10克 的物品
3. 每次可以不拿或全拿，问最高价值是多少

    编号 重量(g)  价值(元)                        简称
    1   4       1600           黄金N块            A
    2   8       2400           红宝石N粒          R
    3   5       30             白银N块            S
    0   1       1_000_000      钻石N粒            D
*/

    private static class Item {
        public int index;
        public String name;
        public int weight;
        public int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }
    }


    public static int getMaxValue(Item[] items, int total) {
        int[][] dp = new int[items.length][total + 1];
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) {
            if (j >= item0.weight) {
                dp[0][j] = dp[0][j - item0.weight] + item0.value;
            }
        }
        for (int i = 1; i < items.length; i++) {
            for (int j = 0; j < total + 1; j++) {
                Item item = items[i];
                int x = dp[i - 1][j];
                if (j >= item.weight) {
                    dp[i][j] = Math.max(x, dp[i][j - item.weight] + item.value);
                } else {
                    dp[i][j] = x;
                }
            }
        }
        return dp[items.length - 1][total];
    }
}